package com.lsa.letcode.the46.permutations;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
	public List<List<Integer>> permute(int[] seq) {
		List<List<Integer>> seqs = new ArrayList<List<Integer>>();
        Arrays.sort(seq);
        
        seqs.add(toList(seq));
        
        while(nextPermutation(seq)) {
        	seqs.add(toList(seq));
        }
        
        return seqs;
	}
	
	private List<Integer> toList(int[] seq) {
		List<Integer> l = new ArrayList<Integer>();
		for (int i : seq) {
			l.add(i);
		}
		return l;
	}

    public boolean nextPermutation(int[] num) {
    	if (num.length < 2) {
    		return false;
    	}
    	int i;
    	for (i = num.length - 2; i > -1; --i) {
			if (num[i] < num[i + 1]){
				break;
			}
		}
    	if (i == - 1){
    		reverse(num);
    		return false;
    	}
    	else {
    		int j = i + 1;
    		int minIdx = j;
    		// find j s.t. num[i] < num[j] and num[j] is min
    		for (;j < num.length; j++) {
    			if (num[i] < num[j]) {
    				minIdx = j;
    			}
    			else {
    				break;
    			}
			}
    		swap(num, i, minIdx);
			reverse(num, i + 1, num.length - 1);
    	}
    	
    	return true;
    }
    
    void swap(int[] arr, int from, int to) {
		int t = arr[from];
		arr[from] = arr[to];
		arr[to] = t;
    }
    
    void reverse(int[] arr, int from, int to) {
    	int len = to - from + 1;
    	for (int i = from; i < from + len / 2; i++) {
    		int j = to - (i - from);
    		int t = arr[i];
    		arr[i] = arr[j];
    		arr[j] = t;
		}
    }
    
    void reverse(int[] arr) {
    	reverse(arr, 0, arr.length - 1);
    }
}